package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author Administrator
 * @date 2020/6/17 14:47
 */
public class Cake {
    /**
     * 切割后面积最大的蛋糕
     * 矩形蛋糕的高度为 h 且宽度为 w，
     * 给你两个整数数组 horizontalCuts 和 verticalCuts，
     * 其中 horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离，
     * 类似地， verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。
     * 请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，
     * 请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，
     * 因此需要将结果对 10^9 + 7 取余后返回。
     * 2 <= h, w <= 10^9
     * 1 <= horizontalCuts.length < min(h, 10^5)
     * 1 <= verticalCuts.length < min(w, 10^5)
     * 1 <= horizontalCuts[i] < h
     * 1 <= verticalCuts[i] < w
     * 题目数据保证 horizontalCuts 中的所有元素各不相同
     * 题目数据保证 verticalCuts 中的所有元素各不相同
     */
    @Test
    public void maxArea() {
        Assert.assertEquals(4, maxArea(5, 4, new int[]{1, 2, 4}, new int[]{1, 3}));
        Assert.assertEquals(6, maxArea(5, 4, new int[]{3, 1}, new int[]{1}));
        Assert.assertEquals(9, maxArea(5, 4, new int[]{3}, new int[]{3}));
    }

    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        long maxH = (maxDistance(h, horizontalCuts));
        long maxW = (maxDistance(w, verticalCuts));
        return (int) ((maxH * maxW) % 1000000007);
    }

    private long maxDistance(int len, int[] cut) {
        Arrays.sort(cut);
        long max = Math.max(cut[0], len - cut[cut.length - 1]);
        for (int i = 1; i < cut.length; i++) {
            max = Math.max(max, cut[i] - cut[i - 1]);
        }
        return max;
    }
}
